package leetcode.top100;

/**
 * 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。
 *
 * 找出只出现一次的那两个元素。
 *
 * 示例 :
 *
 * 输入: [1,2,1,3,2,5]
 * 输出: [3,5]
 * 注意：
 *
 * 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
 * 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
 *
 */
public class Code260_AppearOnlyOnce2 {
    public int[] singleNumber(int[] nums) {
        if(nums == null || (nums.length & 1) != 0)return new int[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res ^= nums[i];
        }
        int bitIndex = 1;
        while ((res & bitIndex) == 0) bitIndex <<= 1;
        int res1 = 0;//与0异或结果不变
        int res2 = 0;
        for (int i = 0; i < nums.length; i++) {
            //第bitIndex位相同
            if((nums[i] & bitIndex) == 0){
                res1 ^= nums[i];
            }else {
                res2 ^= nums[i];
            }
        }
        return new int[]{res1,res2};
    }
}
